package com.xhd.demo.concurrent;

public class QuickSort {
    public static void sort(int[] array, int first, int last) {
       if(first >= last) {
           return;
       }
       int i = first, j = last;
       int temp = array[i];
       while (i < j) {
           while (temp <= array[j] && i < j) {
               j--;
           }
           while (temp >= array[i] && i < j) {
               i++;
           }
           if (i < j) {
               int t = array[i];
               array[i] = array[j];
               array[j] = t;
           }
       }
        if (i == j) {
            array[first] = array[i];
            array[i] = temp;
        }
       sort(array, first, i - 1);
       sort(array, i + 1, last);
    }

    public static int partion(int[] array, int first, int last) {
        int temp = array[first];
        while (first < last) {
            while (first < last && temp <= array[last]) {
                last--;
            }
            if (first < last) {
                array[first] = array[last];
                first++;
            }
            while (first < last && temp >= array[first]) {
                first++;
            }
            if (first < last) {
                array[last] = array[first];
                last--;
            }
        }
        array[first] = temp;
        return first;
    }

    public static void tSort(int[] a) {
        sort(a, 0, a.length - 1);
        System.out.println("sort1 \n");
        for (int i: a) {
            System.out.print(i + ",");
        }
        System.out.println("\n");
    }

    public static void tSort2(int[] a, int first, int last) {
        if (first < last) {
            int middlepos = partion(a, first, last);
            tSort2(a, 0, middlepos - 1);
            tSort2(a, middlepos + 1, last);
        }
        System.out.println("sort2 \n");
        for (int i: a) {
            System.out.print(i + ",");
        }
        System.out.println("\n");
    }

    public static void main(String[] args) {
        int[] array = {5,1,2,7,8,12,35,3,0,6};
        tSort(array);
        int[] array2 = {5,1,2,7,8,12,35,3,0,6};

        tSort2(array2, 0, array2.length - 1);

    }
}
